﻿//https://leetcode.cn/problems/longest-palindromic-substring/description/

class Solution
{
	public :
	string longestPalindrome(string s)
	{
		// 中⼼扩展算法
		int begin = 0, len = 0, n = s.size();
		for (int i = 0; i < n; i++) // 依次枚举所有的中点
		{
			// 先做⼀次奇数⻓度的扩展
			int left = i, right = i;
			while (left >= 0 && right < n && s[left] == s[right])
			{
				left--;
				right++;
			} 
			if(right - left - 1 > len)
			{
				begin = left + 1;
				len = right - left - 1;
			} 
			// 偶数⻓度的扩展
				left = i, right = i + 1;
			while (left >= 0 && right < n && s[left] == s[right])
			{
				left--;
				right++;
			} 
			if(right - left - 1 > len)
			{
				begin = left + 1;
				len = right - left - 1;
			}
		} return s.substr(begin, len);
	}
};